package com.example.algorithms.sort;

/**
 * @Author Zhang Jie
 * @Date 9/28/20
 * @Version 1.0
 */

import java.util.Comparator;

/**
 * 归并排序
 * 分治,递归
 * 将数组分成前后两部分,然后对两部分分别进行排序,排序好之后再将两部分合在一起
 *
 * 稳定
 * 无论最好最坏还是平均情况,都是O(nlogn)
 * 不是原地排序,需要额外的存储空间,空间复杂度为O(n)
 *
 * 由下到上，先处理子问题，然后对子问题的解再合并
 *
 * @author jane
 */
public class MergeSort {

    /**
     * 从小到大排序,递归
     * @param arr
     * @return
     */
    public static int[] sortUp(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }

        _sort(arr,0,arr.length-1,(x,y)->y-x);

        return arr;
    }

    /**
     * 从大到小排序
     * @param arr
     * @return
     */
    public static int[] sortDown(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }

        _sort(arr,0,arr.length-1,Comparator.comparingInt(x -> x));

        return arr;
    }

    public static int[] _sort(int[] arr, int begin, int end, Comparator<Integer> comparator){
        if(end<=begin){
            return arr;
        }

        int mid = (end+begin+1)/2;

        _sort(arr,begin,mid-1, comparator);
        _sort(arr,mid,end, comparator);

        _merge(arr,begin,end, comparator);

        return arr;
    }

    public static int[] _merge(int[] arr, int begin, int end, Comparator<Integer> comparator){

        int mid=(end+begin+1)/2;

        //[begin,begin+mid-1],[begin+mid,end]
        int left=begin;
        int leftEnd=mid-1;
        int right=mid;
        int count=0;

        int[] copy=new int[end-begin+1];

        while(left<=leftEnd&&right<=end){
            copy[count++]=comparator.compare(arr[left],arr[right])>0?arr[left++]:arr[right++];
        }
        while(left<=leftEnd){
            copy[count++]=arr[left++];
        }
        while (right<=end){
            copy[count++]=arr[right++];
        }

        System.arraycopy(copy,0,arr,begin,end-begin+1);

        return arr;
    }
}
